package com.atguigu.linkedlist;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//其实递归就是程序内部维护了一个栈。这个题就是每次都把最小值压入栈，最后出栈的时候，将所有数连在一起就可以了。
// 说白了，就是用一个栈维护了顺序。最后的连接，当然是小的连小的，所以l1 小，就连到 l1,l2 小就连到 l2，最后先返回的，
// 就是最小的头结点

    //递归解法
class MergeTwoSortedLists {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2 ;
        } else if (list2 == null) {
            return list1 ;
        }  else if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next,list2) ;
            return list1 ;
        } else {
            list2.next = mergeTwoLists(list2.next,list1) ;
            return list2 ;
        }
    }
}


